package main.old.new_2023.last.month_7;


import main.dataStruct.Node;

/**
 * @Description:
 * todo 445. 两数相加 II
 * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 * todo 剑指 Offer 36. 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0703 {
    Node head, pre;
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        dfs(root);

        pre.right = head;
        head.left =pre;//进行头节点和尾节点的相互指向，这两句的顺序也是可以颠倒的

        return head;

    }

    public void dfs(Node cur){
        if(cur==null) return;
        dfs(cur.left);

        //pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur,当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点
        if(pre==null) head = cur;
            //反之，pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。
        else pre.right = cur;

        cur.left = pre;//pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。

        pre = cur;//pre指向当前的cur
        dfs(cur.right);//全部迭代完成后，pre指向双向链表中的尾节点
    }

    //两数之和
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //逻辑就是翻转列表 + 两数相加
        l1 = reverseList(l1);
        l2 = reverseList(l2); // l1 和 l2 反转后，就变成【2. 两数相加】了
        ListNode l3 = addNode(l1, l2, 0);
        return reverseList(l3);
    }
    private ListNode reverseList(ListNode listNode){
        if (listNode == null || listNode.next == null){
            return listNode;
        }
        ListNode reverseNode = reverseList(listNode.next);
        listNode.next.next = listNode;
        listNode.next = null;
        return reverseNode;
    }
    private ListNode addNode(ListNode l1, ListNode l2,int carry){
        if (l1 == null && l2 == null){
            return carry != 0 ? new ListNode(carry) : null;
        }
        if (l1 == null){
            l1 = l2;
            l2 = null;
        }
        carry =carry  + ( l1.val + (l2 != null ? l2.val : 0)); // 节点值和进位加在一起
        l1.val = carry % 10; // 每个节点保存一个数位
        l1.next = addNode(l1.next, (l2 != null ? l2.next : null), carry / 10); // 进位
        return l1;
    }


    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
